package com.eddie.tenalgorithm.kruskalcase;

import lombok.Data;

import java.util.ArrayList;
import java.util.Collections;

/**
 * @author Eddie
 * @date 2022/08/16 14:54
 **/
@Data
public class KruskalCase {
    /**
     * 边的个数
     */
    private int edgeNum;
    /**
     * 顶点数组
     */
    private char[] vertexs;
    /**
     * 邻接矩阵
     */
    private int[][] matrix;
    /**
     * 顶点个数
     */
    private int vLen;
    /**
     * 使用INF表示两个顶点不能连通
     */
    private static final int INF=Integer.MAX_VALUE;

    public static void main(String[] args) {
        char[] vertexs={'A','B','C','D','E','F','G'};
        //克鲁斯卡尔算法的邻接矩阵
        int[][] matrix = {
                /*A*//*B*//*C*//*D*//*E*//*F*//*G*/
                /*A*/ { 0, 12, INF, INF, INF, 16, 14},
                /*B*/ { 12, 0, 10, INF, INF, 7, INF},
                /*C*/ { INF, 10, 0, 3, 5, 6, INF},
                /*D*/ { INF, INF, 3, 0, 4, INF, INF},
                /*E*/ { INF, INF, 5, 4, 0, 2, 8},
                /*F*/ { 16, 7, 6, INF, 2, 0, 9},
                /*G*/ { 14, INF, INF, INF, 8, 9, 0}};
        //创建KruskalCase对象实例
        KruskalCase kruskalCase = new KruskalCase(vertexs, matrix);
        //输出构建的邻接矩阵
        kruskalCase.print();

        System.out.println("最小生成树="+kruskalCase.kruskal());
    }

    /**
     * 构造器
     * @param vertexs 顶点数组
     * @param matrix 邻接矩阵
     */
    public KruskalCase(char[] vertexs, int[][] matrix) {
        //初始化顶点数和边的个数
        vLen=vertexs.length;
        //初始化顶点,深拷贝
        this.vertexs=new char[vLen];
        System.arraycopy(vertexs, 0, this.vertexs, 0, vertexs.length);

        //初始化边,深拷贝
        this.matrix=new int[vLen][vLen];
        //初始化边数
        edgeNum=0;
        for (int i = 0; i < vLen; i++) {
            for (int j = i+1; j < vLen; j++) {
                this.matrix[i][j]=matrix[i][j];
                if(matrix[i][j]!=INF&&matrix[i][j]!=0){
                    edgeNum++;
                }
            }
        }
    }

    public ArrayList<EData> kruskal(){
        //用于保存"已有最小生成树"中的每个顶点在最小生成树的终点
        int[] ends=new int[vLen];
        //初始化ends数组，让顶点先都指向自己
        for (int i = 0; i < ends.length; i++) {
            ends[i]=i;
        }
        //创建结果集合，保存最后的最小生成树
        ArrayList<EData> res = new ArrayList<>();

        //获取图中的所有边的集合，一共有12条边
        ArrayList<EData> edges = getEdges();
        //按照边的权值大小进行排序
        Collections.sort(edges);

        System.out.println("图边的集合="+edges);
        //表示最后结果的索引
        int index=0;
        while(res.size()<vLen-1){
            //当前边
            EData eData = edges.get(index++);
            //当前start顶点
            int start = getEnd(ends, getPosition(eData.start));
            //当前end顶点
            int end = getEnd(ends, getPosition(eData.end));
            if(start!=end){
                //如果两个顶点的所连结点最终结点，也就是这个当前结点所在树的根节点不相同
                //则这条边加入结果集，并将start的根节点指向end的根节点
                res.add(eData);
                ends[start]=ends[end];
            }
        }

        return res;
    }
    /**
     * 打印邻接矩阵
     */
    public void print(){
        System.out.println("邻接矩阵为：\n");
        for (int i = 0; i < vertexs.length; i++) {
            for (int j = 0; j < vertexs.length; j++) {
                System.out.printf("%-10d\t",matrix[i][j]);
            }
            System.out.println();
        }
    }

    /**
     *
     * @param ch 顶点的值，比如'A','B'
     * @return 返回ch顶点对应的下标，如果找不到就返回-1
     */
    private int getPosition(char ch){
        for (int i = 0; i < vertexs.length; i++) {
            //找到
            if(vertexs[i]==ch){
                return i;
            }
        }
        //找不到返回-1
        return -1;
    }

    /**
     * 功能：获取图中的边，放到EData[] 数组中，后面我们需要遍历该数组
     * 是通过matrix 邻接矩阵来获取
     * EData[] 样式[['A','B',12],['B','F',7],['','',]]
     */
    private ArrayList<EData> getEdges(){
        ArrayList<EData> eData = new ArrayList<>();
        for (int i = 0; i < vertexs.length; i++) {
            for (int j=i+1;j<vertexs.length;j++){
                if(matrix[i][j]!=INF){
                    eData.add(new EData(vertexs[i],vertexs[j],matrix[i][j]));
                }
            }
        }
        return eData;
    }

    /**
     * 功能：获取下标为i的顶点的终点，用于后面判断两个顶点的终点是否相同
     * @param ends:数组就是记录了各个顶点对应的终点是哪个，ends数组是在遍历过程中，逐步形成
     * @param i：表示传入的顶点对应的下标
     * @return 返回的就是下标为i的顶点对应的终点的下标
     */
    private int getEnd(int[] ends,int i){
        while (i!=ends[i]) {
            ends[i]=ends[ends[i]];
            i=ends[i];
        }
        return i;
    }
}

/**
 * 创建一个类EData,它的对象实例就表示一条边
 */
class EData implements Comparable<EData>{
    /**
     * 边的一个点
     */
    char start;
    /**
     * 边的另外一个点
     */
    char end;
    /**
     * 边的权值
     */
    int weight;

    /**
     * 构造器
     * @param start  一个点
     * @param end  另一个点
     * @param weight 权值
     */
    public EData(char start, char end, int weight) {
        this.start = start;
        this.end = end;
        this.weight = weight;
    }

    @Override
    public String toString() {
        return "EData{" +
                "start=" + start +
                ", end=" + end +
                ", weight=" + weight +
                '}';
    }

    @Override
    public int compareTo(EData o) {
        return this.weight-o.weight;
    }
}
